1. Field of the Invention
This invention relates to the time sharing of user defined devices in a multi-tasking computer system and, in particular, to the flow control of commands of user defined devices connected to the system through the memory management unit.
2. Art Background
Computers range in size, features, and capabilities from personal computers to large mainframes. Many computers are capable of multi-tasking; that is, the processes running on the system share the resources of the system, e.g. CPU, co-processor, memory and devices, so the more than one process can be running or appear to be running concurrently. The multi-tasking capability is achieved through the "sharing" (also referred to as "time-sharing") of the resources by the processes. The operating system gives each process a turn to utilize the resources, typically for a predetermined amount of time. When it is another process's turn to utilize the resource, the current process is suspended; and the state of the process is stored until it is the process's turn again to utilize the resource. For example, in some UNIX-based systems, a scheduler allocates the CPU and co-processor, such as a floating point processor (FPU), to processes. It schedules the processes to run in turn until they voluntarily relinquish the CPU and FPU while awaiting another resource or until the operating system preempts the process when the run time exceeds a time quantum.
When the operating system switches the CPU or CPU's (if the system is configured with multiple CPU's) from process to process it has to save the state of the process which is not currently running (such a process is referred to as "inactive") so that when the operating system switches the CPU back to run an inactive process (the inactive process thereby becoming "active"), the process will resume its execution at the point it was stopped earlier. The information that needs to be saved and restored in order to resume execution in the same state in which the process was earlier stopped is referred to as the context of the process. When executing a process, the system is said to be executing in the context of the process. Thus, when the operating system determines that it should execute another process, it performs what is referred to as a "context switch" so that the system can execute in the context of the other process. The context switch comprises the steps of saving the context of the active process which had been running at the time of the context switch and restoring the context of the inactive process to be activated so that process will resume at the point it was stopped by an earlier context switch. The context contains such information as the values of the process's global user variable and data structures, the valves of machine registers which the process uses, and other data that may be needed to continue the running of the process at a later time.
Context switching is illustrated in the diagram of FIG. 1. At time t0, Process1 is active and processes 2 and 3 are inactive. At time t1, a context switch is performed in which the context of the CPU and FPU with respect to Process1 is stored in the operating system data structure (In a UNIX-based operating system, this data structure typically comprises a system process table and save area.) and the context of the CPU and FPU with respect to Process2 is retrieved from the operating system data structure and restored on the CPU and FPU so that the CPU and FPU resume their execution in the context of Process2. Similarly, at time t2 a context switch is performed in which the context of the CPU and FPU with respect to Process2 is stored in the operating system data structure and the context of the CPU and FPU with respect to Process3 are restored on the CPU and FPU.
The computer systems currently available typically support the CPU and FPU as devices which are time-shared among processes. Thus, the operating system recognizes the two devices and knows what elements comprise the state of the processor to be preserved when context switching is performed. Additional processors or devices are often connected to the system through the memory management unit (MMU) using a well known technique referred to as memory mapped input/out (I/O). Each device connected through the MMU has an address state which represents the public state a process can access. The CPU accesses the device using the address in the same manner as if the device were memory.
As the sophistication of computer systems increase, so do the number of specialized devices or processors (hereinafter collectively referred to as "user defined devices") which perform specific, typically time consuming, functions thereby distributing the processing load and increasing the overall processing speed of the system. These user defined devices are typically attached to the system through the MMU. For example, many computer systems utilize graphics processors to perform the time consuming computations required to generate a graphic display or vector processors to perform vector calculations. However, the operating system cannot utilize the same techniques and processes which are used to provide a full multi-tasking capability of the CPU and FPU to provide a multi-tasking capability of the user defined devices because the context and characteristics of each device is different. Thus, the increase in speed provided by the user defined devices is minimized by absence of a time share capability among multiple processes.
Several problems arise when multiple processes access user defined devices which are connected through the MMU. One problem arises with respect to the context switching the device. Although multiple processes have access to the same user-defined device, only one process can access the device at a time regardless of what context the kernel is operating in because the kernel does not provide for the context switching of a device connected to the system through the MMU. Thus, a process which accesses a device through the MMU controls the device until it is finished accessing the device.
The problem that arises is best described by example. Two processes, Process1 and 2, are currently running on the system and both process utilize a device such as a vector processor which is connected through the MMU. Process1 has control of the CPU and is the active process. Process1 attempts to access the device first by checking the device lock to see if access to the device is permitted. If the device lock is set, Process1 is not be able to access the device and has to wait, i.e., go to "sleep", until the device is not locked and Process1 is the active process. If the device lock is not set, Process1 sets the device lock to prevent any other process from accessing the device and loads the device with the context information required for the device to operate with Process1. If a process switch occurs which renders Process1 inactive and Process2 active, when Process2 attempts to access the device, it will discover that the device is locked because Process1 has not finished accessing the device. Thus, Process2 will have to go to sleep until Process1 is finished accessing the device. When Process1 is finished accessing the device, the context information from Process1 is read from the device and stored in a system data structure, such as the save area in the UNIX operating system, and the device is unlocked, thereby permitting other processes to access the device.
Another problem arises when the operating system receives a command from a process to be assembled and subsequently sent to the device to complete execution of the command. The command when assembled may consist of multiple words containing various attributes of the command. Errors occur when control of the CPU switches from a first process to a second process and the entire command had not been transferred to the device. The command is lost because the process does not realize that the complete command was not transferred to the device, and therefore the process will not retransfer the command when the process subsequently has control of the CPU. Furthermore the operating system has no mechanism to save the command which is partially loaded into the device.
Still another problem arises with respect to the control of process flow. To control the flow and execution of a number of commands with respect to a particular device, a queue is typically used to store the commands in sequence and send one command at a time to the device. However, the queue is of a limited size and can overflow, thereby losing those commands which cannot be stored in the overflow queue. This problem can be decreased somewhat by providing a separate device queue for each process that accesses the device. However, overflow problems can still occur if the process accesses the device frequently.
Serialization and synchronization problems also arise with respect to devices connected through the MMU. Serialization problems occur when a process executes two commands with respect to the same device, and the first command is transmitted through the queue so that it reaches the device after the second command which is not transmitted through the queue. Synchronization problems arise when multiple processes interact with one another and require that one process execute certain commands with respect to a device before another process executes commands. For example, if the device connected through the MMU is a graphics device and Process1 contains commands to load the color table while Process2 contains commands to draw a graphics image, the Process1 command has to be executed prior to the Process2 commands in order that the proper colors are utilized to portray the graphics image.